1. Field of the Invention
The present invention relates to methods and apparatus for storing and manipulating multidimensional data, and more particularly, the present invention relates to database structures and methods wherein spatial data is managed within the framework of a relational database system.
2. Art Background
The position of a single point in space may be defined by multiple values. This "multidimensional data" may represent georeferenced data from hydrologic or geologic surveys, space based data collected from orbital or interplanetary spacecraft, data utilized by computer aided design (CAD) systems as well as multidimensional business data such as data required for decision support systems or on-line analytical processing systems. Depending on the environment, the data may have a high or low relative spatial content. For example, hydrographic or cartographic data is almost exclusively spatial because each record includes latitude, longitude, elevation/depth, and occasionally time as a measurement. In other instances, the spatial content may be relatively low, for example, in a customer information database where a location in the database may relate to one of many possible bits of data pertaining to a customer.
The storage and manipulation of spatial data in a traditional relational database management system presents a variety of problems. Since the relational database management system ("RDBMS") is unidimensional, each value relating to a multidimensional point must be maintained in a separate column within the database. By maintaining each value in a separate column, the organization of the spatial data is not maintained. In addition, searching for data points in a given multidimensional space requires a significant amount of computation using a relational database structure. In the case of very large relational databases used to store spatial data, the column by column range search required to locate and manipulate spatial data is computationally intensive and relatively slow.
Attempts to resolve the problem of storing and managing spatial data in relational database systems have resulted in hybrid solutions. From the perspective of the relational database model, the use of relational database systems for spatial data is inefficient. As shown in FIG. 1, one hybrid approach includes two side-by-side database engines, namely, a relational database management system 50 and a spatial database system 55. The RDBMS 50 maintains attribute data which is non-spatial. An example of attribute data is the value of temperature or ocean salinity for a three dimensional point in the Pacific Ocean. Another example of non-spatial attribute data is the cosmic ray flux through a point in space between the Earth and Mars. As illustrated in FIG. 1, the RDBMS 50 is linked to a spatial database 55 which references or links the corresponding spatial data through spatial indexes 57. One example of an existing hybrid system is a RDBMS manufactured by Oracle Corporation linked to a spatial database referred to as ARC/Info. The Oracle-ARC/Info hybrid database is used to store and manage cartographic projections and similar spatial data in conjunction with attributes related to the spatial data.
A primary disadvantage of the hybrid approach illustrated in FIG. 1 is the requirement of maintaining two discrete database engines as well as a proprietary data structure utilizing unique spatial indexes. Accordingly, the hybrid system does not provide an open distributed database architecture which is easily transportable from one hybrid application to another. In addition, as the size of the database increases, so does the size and complexity of the index. Eventually, the computational "overhead" of maintaining this index results in rapidly deteriorating performance when loading new data and updating existing database records.
The hybrid approach illustrated in FIG. 1 has been applied to geographic information systems ("GIS") which have been created to manipulate spatial objects using a limited two dimensional implementation. Several such hybrid systems exist, each with its own unique proprietary techniques for defining and manipulating spatial data. It is therefore difficult for the user of one system to access data in another because format for data storage is incompatible. This has lead to the development of "exchange" standards that define a "standard data format" which enables reading of data created in one system by another when it passes through this intermediate translation into/out of an exchange format. The result is a "spaghetti net" data infrastructure of proprietary data formats that exchange data with other systems via cumbersome translation to and from exchange formats.
The present invention provides an improved method and apparatus for storing, manipulating, and retrieving spatial and non-spatial data in a database. The present invention includes an improvement to a data structure referred to as hydrographic hyperspatial code ("HH Code"). The basic HH Code data structure was originally disclosed by H. P. Varma in a paper entitled "A Structure for Spatial-Temporal Databases", International Hydrographic Review, Monaco LXVII (1) (January, 1990) (hereinafter the "Varma paper"). HH Code as taught by Varma is a data structure which is based on a linearization technique which maintains the dimensional organization of multidimensional data within the data itself, thereby providing significant advantages over either the hybrid or traditional RDBMS data structures.
As will be described, the present invention is an improvement to the original HH Code data structure disclosed in the Varma paper. The present invention's implementation and utilization of binary hyperspatial ("BH code") overcomes the inherent limitations of prior art RDBMS in efficiently storing, manipulating and retrieving spatial data. The present invention's database method and apparatus provides for the seamless handling of both spatial and non-spatial data in the same database, and constitutes a fundamental improvement in the field of database structures and management.